package zuo.middleLevel_1;

import com.sun.xml.internal.bind.v2.model.core.ID;
import javafx.scene.layout.VBox;
import org.omg.CORBA.MARSHAL;
import tools.generRandomBuff.RandomBuff;

import java.util.ArrayList;
import java.util.Arrays;

/**
 * @Author: Forx
 * @Data: 2021/6/21
 * @Desc: Algorithm - zuo.middleLevel_1
 * @Version: v1.0
 */
public class middleLevel_1 {
    /**
     * 给定一个有序数组arr,代表数轴上从左到右有n个点arr[0]、arr[1]...arr[n-1],
     * 给定一个正数L,代表一根长度为L的绳子，求绳子最多能覆盖其中的几个点。
     *
     * arr[0] 是第0个点在数轴上的位置,如arr={0,1,3,4,56}
     * 第0点在x=0;第1点在x=1,第2点在x=3,第三点在x=4,第四点在x=56
     * 如果L=1,则L的右端点在1处包含的点最多可以包含0点和1点
     *
     *
     * */
    /*
    * O(n^2)
    * */
    public static int getNods_Force(int[] arr,int L){
        int index = 0;
        int maxNum = 0;
        for (int i = 0; i < arr.length; i++) {
            for (int j = i; j < arr.length; j++) {
                if(arr[j] <= L+arr[i]){
                    index++;
                }else {
                    break;
                }
            }
            if(maxNum < index){
                maxNum = index;
            }
            index = 0;

        }
        return maxNum;
    }
    /**
     *  由于是有序表,我们还可以找到
     *
     * */
    /**
     * 因为未产生回退现象所以复杂度是O(N)
     * */
    public static int getNods_OPT(int[] arr,int L){
        int index = 0;
        int maxNum = 1;
        for (int i = 0; i <= arr.length-maxNum; i++) {
            for (int j = i+maxNum; j < arr.length; j++) {
                if(arr[j] <= L+arr[i]){
                    index++;
                }else {
                    break;
                }
            }
            if( index>0){
                maxNum += index;
            }
            index = 0;
        }
        return maxNum;
    }

    /**
     * 小虎去附近的商店买苹果，奸诈的商贩使用了捆绑交易，只提供6个每袋和8个
     * 每袋的包装包装不可拆分。可是小虎现在只想购买恰好n个苹果，小虎想购买尽
     * 量少的袋数方便携带。如果不能购买恰好n个苹果，小虎将不会购买。输入一个
     * 整数n,表示小虎想购买的个苹果，返回最小使用多少袋子。如果无论如何都不
     * 能正好装下，返回-1。
     * */
    public static int getMinBugs(int res){
        if(res<0 || res%2==1)return -1;
        if(res==0){
            return 0;
        }
        int got6 = getMinBugs(res-6);
        int got8 = getMinBugs(res-8);
        if(got6==-1 && got8==-1){
            return -1;
        }else if(got6==-1){
            return got8+1;
        }else if(got8==-1){
            return got6+1;
        }else {
            return Math.min(got6,got8)+1;
        }
    }
    public static int getMinBugsM1(int res){
        if(res%2==1)return -1;
        int bag6 = -1;
        int bag8 = res/8;
        int rest = res % 8;
        while (bag8>=0 && rest < 24){
           int resbag6 = base6Bags(rest);
            if(resbag6!=-1){
                bag6 = resbag6;
                return bag8+bag6;
            }
            rest = res - 8*(--bag8);
        }
        return -1;


    }
    public static int base6Bags(int n){
        return n%6==0?n/6:-1;
    }
    /**
     * 这个是根据输入输出的数据找到的规律,纯粹是为了凑答案
     * 这就是打表法
     * */
    public static int minBagAwesome(int apple) {
        if ((apple & 1) != 0) return -1;
        if (apple < 18) {
            return apple == 0 ? 0 : (apple == 6 || apple == 8) ? 1
                    : (apple == 12 || apple == 14 || apple == 16) ? 2 : -1;

        }
        return (apple - 18) / 8 + 3;
    }
    /**
     *
     * 两个动物吃草,每个动物吃的草的数量必须是4的整数次幂
     * 给定草的树木,谁先吃完草谁赢
     * 如给两根草,先手先吃,只能吃1根,后手再吃一根吃完,后手赢
     * 返回1是先手赢,2是后手赢
     * */
    public static int eatGrassWinner(int grass){
        if(grass < 5){
            return (grass==0 || grass==2)? 2:1;
        }
        int base = 1;
        while (base<=grass){
            if(eatGrassWinner(grass-base)==2){
                return 1;
            }
            if(base>grass/4)break;
            base*=4;
        }
        return 2;
    }
    /**
     * 经测试发现输出是循环的 分别是2 1 2 1 1
     * 因此有下面的代码
     *
     * */
    public static int eatGrassAwesome(int grass){
        int index = (grass%5);
        return (index==0 || index==2)?2:1;
    }

    /**
     * 牛牛有一些排成一行的正方形。每个正方形已经被染成红色或者绿色。牛牛现在可
     * 以选择任意一个正方形然后用这两种颜色的任意一种进行染色，这个正方形的颜色将
     * 会被覆盖。牛牛的目标是在完成染色之后，每个红色R都比每个绿色G距离最左侧近。
     * 牛牛想知道他最少需要涂染几个正方形。
     * 如样例所示：s=RGRGR
     * 我们涂染之后变成RRRGG满足要求了，涂染的个数为2,没有比这个更好的涂染方案。
     * 我们用1代表Red 2代表Green
     * 尽量让所有的1在左边,2在右边
     * */
    //O(n^2)
    public static int minChangeColor(int[] arr){
            int minChanges = Integer.MAX_VALUE;
            int changeCnt = 0;
        for (int i = 0; i < arr.length; i++) {
            changeCnt = calNums(arr,0,i,1) + calNums(arr,i,arr.length,2);
            if(changeCnt < minChanges){
                minChanges = changeCnt;
            }
        }
        return minChanges;

    }
    //O(n)
    public static int minChangeColorOPT(int[] arr){
        int minChanges = Integer.MAX_VALUE;
        int changeCnt = 0;
        int[] left1 = new int[arr.length];
        int[] right2 = new int[arr.length];
        for (int i = 0; i < arr.length; i++) {
            left1[i] = calNums(arr,0,i,1);
        }
        for (int i = 0; i < arr.length; i++) {
            right2[i] = calNums(arr,i,arr.length,2);
        }
        for (int i = 0; i < arr.length; i++) {
            //changeCnt = calNums(arr,0,i,1) + calNums(arr,i,arr.length,2);
            changeCnt = left1[i] + right2[i];
            if(changeCnt < minChanges){
                minChanges = changeCnt;
            }
        }
        return minChanges;

    }
    public static int calNums(int[] arr,int left,int right,int kind){
        int cnt = 0;
        for (int i = left; i <right ; i++) {
            if(arr[i] == kind){
                cnt++;
            }
        }
        return cnt;
    }

    /**
     * 给定一个N米N的矩阵 matrix,只有0和1两种值,返回边框全是1的最大正方形的边
     * 长长度
     * 例如
     * 01111
     * 01001
     * 01001
     * 01111
     * 01011
     * 其中边框全是1的最大正方形的大小为4*4,所以返回4。
     *
     * */
    //O(n^4),理论上的复杂度应该是O(n^3),多出来的一个n次方是耗费在验证方面
    //我们可以优化验证的方式
    public static int getMaxMatrix(int[][] arr){
          int cols = arr.length;
          int rows = arr[0].length;
          int maxBorder = Integer.MIN_VALUE;
          int maxBorderX = -1;
          int maxBorderY= -1;
        for (int i = 0; i < rows; i++) {
            for (int j = 0; j < cols; j++) {
                if(arr[i][j] == 0)continue;
                for (int border = 1; border <=Math.min(rows-i,cols-j); border++) {
                    if(verifyMatrix(arr,i,j,border) && border>maxBorder){
                        maxBorder = border;
                        maxBorderX = j;
                        maxBorderY = i;
                    }
                }
            }
        }
        System.out.println("maxBorderX = " + maxBorderX);
        System.out.println("maxBorderY = " + maxBorderY);
        System.out.println("maxBorder = " + maxBorder);

        return 0;
    }
    public static boolean verifyMatrix(int[][] arr,int i,int j,int border){
        for (int k = i; k < border; k++) {
            if(arr[k][j]==0)return false;
        }
        for (int k = j; k < border; k++) {
            if(arr[i][k]==0)return false;
        }
        for (int k = j; k < border; k++) {
            if(arr[i+border-1][k]==0)return false;
        }
        for (int k = i; k < border; k++) {
            if(arr[k][j+border-1]==0)return false;
        }
        return true;

    }
    public static int getMaxMatrixOPT(int[][] arr){
        int cols = arr.length;
        int rows = arr[0].length;
        int maxBorder = Integer.MIN_VALUE;
        int maxBorderX = -1;
        int maxBorderY= -1;
        int[][] right = new int[rows][cols];
        int[][] down = new int[rows][cols];
        if(arr[rows-1][cols-1]==1){
            right[rows-1][cols-1] = 1;
            down[rows-1][cols-1] = 1;
        }
        for (int i = rows-1; i >=0 ; i--) {
            for (int j = cols-1; j >=0 ; j--) {
                if(arr[i][j]==1){
                    if(j+1<cols){
                        right[i][j] = right[i][j+1]+1;

                    }else {
                        right[i][j] = 1;
                    }

                }
            }
        }
        for (int i = cols-1; i >=0 ; i--) {
            for (int j = rows-1;j >=0;j--){
                if(arr[j][i]==1){
                    if(j+1>=rows){
                        down[j][i]=1;
                    }else {
                        down[j][i] = down[j+1][i]+1;
                    }

                }
            }
        }
        for (int i = 0; i < rows; i++) {
            for (int j = 0; j < cols; j++) {
                if(arr[i][j] == 0)continue;
                for (int border = 1; border <=Math.min(rows-i,cols-j); border++) {
                    if(right[i][j] >=border && down[i][j] >=border && right[i+border-1][j] >=border && down[i][j+border-1]>=border && border>maxBorder){
                        maxBorder = border;
                        maxBorderX = j;
                        maxBorderY = i;
                    }
                }
            }
        }
        System.out.println("maxBorderX = " + maxBorderX);
        System.out.println("maxBorderY = " + maxBorderY);
        System.out.println("maxBorder = " + maxBorder);

        return 0;
    }

    /**
     * 给定一个函数f,可以1~5的数字等概率返回一个。请加工出1~7的数字等概率
     * 返回一个的函数g。
     * 给定一个函数f,可以a~b的数字等概率返回一个。请加工出c~d的数字等概率
     * 返回一个的函数g
     * 给定一个函数f,以p概率返回0,以1-p概率返回1。请加工出等概率返回0和1的
     * 函数g
     * */



    public static boolean verifyQuestion1(){
        int testTime = 10000;
        int maxVlaue = 100;
        int maxLen = 10;
        boolean flag = false;
        for (int i = 0; i < testTime; i++) {

            int[] in = RandomBuff.generateRandomBuff(maxVlaue,maxLen);
            Arrays.sort(in);

            int aim = (int)(Math.random()*maxVlaue) ;
            System.out.println(i+"st\t"+"Waitting Test:"+ Arrays.toString(in)+"\taim:"+aim);
            //System.out.println();

            int i1 = getNods_Force(in, aim);
            int i2 = getNods_OPT(in, aim);

            System.out.println("i1 = " + i1);
            System.out.println("i2 = " + i2);
            if(i1!= i2){
                System.out.println("failed");
                break;
            }
            System.out.println();
        }
        return false;
    }
    public static boolean verifyQuestion2(){
        int testTimes = 100000;

        for (int i = 0; i < testTimes; i++) {
            int num = (int)(Math.random()*10000);
            int a1 = minBagAwesome(num);
            int a2 = getMinBugsM1(num);
            System.out.println();
            System.out.println("i:" + i );
            System.out.println("num = " + num);
            System.out.println("a2 = " + a2);
            System.out.println("a1 = " + a1);
            System.out.println();
            if(a1!=a2){

                break;
            }
        }

        return false;
    }
    public static boolean verifyQuestion3(){
        int testTime = 100;
        for (int i = 0; i < testTime; i++) {
            System.out.println("i:"+i + "\twinner:"+eatGrassAwesome(i));
        }
        return false;
    }

    public static void main(String[] args) {
        verifyQuestion1();
        //int[] buff = {2, 10, 46, 46, 59, 63};
        //getNods_OPT(buff,10);
//        verifyQuestion3();
//        int[][] buff = {
//                {0,1,1,1,1},
//                {0,1,1,0,1},
//                {1,1,1,1,1},
//                {1,0,1,1,1},
//                {0,1,0,0,0},
//        };
//        getMaxMatrixOPT(buff);

    }

}
